//
// Created by shenbin on 2022/5/6.
//
#include <unordered_map>

using namespace std;

#ifndef ALGORITHM_TRAINNING_C03_LC146_H
#define ALGORITHM_TRAINNING_C03_LC146_H

class LeetCode146 {
public:
    LeetCode146(int capacity) {
        this->capacity = capacity;
        head = new Node();
        tail = new Node();
        // 保护点
        head->next = tail;
        tail->pre = head;
    }

    int get(int key) {
        if (h.find(key) == h.end()) return -1;
        Node *node = h[key];
        remove(node);
        insert(head, node);
        return node->value;
    }

    void put(int key, int value)
    {
        if(h.find(key) == h.end())
        {
            Node* node = new Node();
            node->value = value;
            node->key = key;
            // 哈希表插入
            h[key] = node;
            // 链表插入
            insert(head, node);
            if (h.size() > this->capacity)
            {
                h.erase(tail->pre->key);
                remove(tail->pre);
            }
        }
        else
        {
            Node* node = h[key];
            node->value = value;
            remove(node);
            insert(head, node);
        }
    }

private:
    struct Node {
        int key;
        int value;
        Node *pre;
        Node *next;
    };
    int capacity;
    unordered_map<int, Node *> h;
    Node *head;
    Node *tail;

    /**
     * 链表删除
     * 链表形如：1 2 3 4 5 6
     * 删除3(node)：
     * 1）2(pre)->next = 4(next) (node->pre->next = node->next)
     * 2) 4(next)->pre = 2(pre) (node->next->pre = node->pre)
     * @param node
     */
    void remove(Node *node) {
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }

    /**
     * 链表插入
     * 链表形如：1 2 3 4 5
     * 在3(p)，插入6(node)
     * 6->next = 3->next (node->next = p->next)
     * 3->next->pre = 6 (p->next->pre = node)
     * 6->pre = 3 (node->pre=p)
     * 3->next = 6 (p->next = node)
     *
     * @param p
     * @param node
     */
    void insert(Node *p, Node *node) {
        p->next->pre = node;
        node->next = p->next;
        p->next = node;
        node->pre = p;
    }
};

#endif //ALGORITHM_TRAINNING_C03_LC146_H
